import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:排序测试
 * User: 阿宾
 * Date: 2024-12-11
 * Time: 09:02
 */
public class SortTest {


    /**
     * 归并排序
     * @param array
     */
    //方法2 非递归
    public static void mergeSort1(int[] array){
        int gap = 1;
        while (gap < array.length){
            for (int i = 0; i < array.length; i += 2*gap) {
                int left = i;
                int mid = left+gap-1;
                int right = mid+gap;
                if(mid >= array.length){
                    mid = array.length-1;
                }
                if(right >= array.length){
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }


    //方法1
    public static void mergeSort(int[] array){
        mergeFun(array,0,array.length-1);
    }

    private static void mergeFun(int[] array, int left, int right) {
        if(left >= right) return;
        int mid = (left + right) / 2;
        mergeFun(array,left,mid);//分解
        mergeFun(array,mid+1,right);//分解
        merge(array,left,mid,right);//合并
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] tmp = new int[right-left+1];

        //接下来对tmp数据进行合并，将合并结果放到array中
        int i = left,j = mid+1,k = 0;
        while (i <= mid && j <= right){
            if(array[i] <= array[j]){
                tmp[k++] = array[i++];
            }else {
                tmp[k++] = array[j++];
            }
        }
        //跳出循环，判断是否有剩余元素
        while (i <= mid){
            tmp[k++] = array[i++];
        }
        while (j <= right){
            tmp[k++] = array[j++];
        }
        //此时tmp是有序的
        for (int i1 = 0; i1 < tmp.length; i1++) {
            array[i1+left] = tmp[i1];
        }
    }

    /**
     * 快速排序
     * @param arr
     */
    //方法2
    private static int partition1(int[] arr, int left, int right) {
        int key = arr[left];
        while (left < right){
            while (left < right && arr[right] >= key)//从右向左找比key小的值
                right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= key)//从左向右找比key大的值
                left++;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
    //方法1
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }
    private static void quick(int[] arr, int left, int right) {
        if(left >= right) return;
        int mid = partition(arr,left,right);
        quick(arr,left,mid-1);
        quick(arr,mid+1,right);
    }
    private static int partition(int[] arr, int left, int right) {
        int key = arr[left];
        int index = left;
        while (left < right){
            while (left < right && arr[right] >= key)//从右向左找比key小的值
                right--;
            while (left < right && arr[left] <= key)//从左向右找比key大的值
                left++;
            swap(arr,left,right);
        }
        swap(arr,index,right);
        return left;
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
            if(!flag){
                return;
            }
        }
    }
    /**
     * 堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){
        //1.建立大根堆
        BuildMaxHeap(arr);
        //2.开始排序
        for (int i = arr.length-1; i > 0 ; i--) {
            swap(arr,i,0);
            AdjustDown(arr,0,i);
        }

    }

    private static void BuildMaxHeap(int[] arr) {
        //将元素位置从0开始计数，而不是从1
        for (int i = (arr.length-1)/2; i >= 0 ; i--) {
            //从分支节点开始调整，将所有子树调整为大根堆
            AdjustDown(arr,i, arr.length-1);
        }
    }

    private static void AdjustDown(int[] elem,int k,int end) {
        int i = 0;
        for (i = 2*k+1;  i < end ; i=i*2+1) {
            //i+1<size是防止数组越界
            if (i + 1 < end && elem[i] < elem[i + 1]) {
                i++;
            }
            //此时i指向的就是最大的孩子节点下标，将最大孩子节点值与根节点值比较
            if (elem[k] > elem[i]) {
                //根节点值比孩子节点值大，符合大根堆，直接跳出循环
                break;
            } else {
                //更新根节点的值，同时更新根节点的指向，
                //继续调整左右子树根节点值最大的子树
                swap(elem,k,i);
                k = i;
            }
        }
    }

    /**
     * 直接选择排序
     * @param arr
     */
    public static void selectSort(int[] arr){
        //固定排序arr.length-1次。最后i=arr.length-2时，已经将最后一个元素排序好了
        for (int i = 0; i < arr.length-1; i++) {
            //每一趟选最小元素
           //将第一个元素看成最小
            int minIndex = i;
            int j = 0;
            for (j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]){
                    minIndex=j;
                }
            }
            if(minIndex != i){
                swap(arr,i,minIndex);
            }
        }
    }
    private static void swap(int[] arr,int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap = arr.length/2;
        for (; gap > 0 ; gap/=2) {
            int tmp = 0;
            for (int i = gap; i < arr.length; i++) {
                int j = 0;
                tmp = arr[i];
                for (j = i-gap; j >= 0 ; j-=gap) {
                    if(arr[j] > tmp){
                        arr[j+gap] = arr[j];
                    }else {
                        break;
                    }
                }
                arr[j+gap] = tmp;
            }
        }
    }
    /**
     * 直接插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){
        int tmp = 0;
        for (int i = 1; i < arr.length; i++) {
            int j = 0;
            tmp = arr[i];
            for (j = i-1; j >= 0 ; j--) {
                if(arr[j] > tmp){//保证排序算法的稳定性
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {10,5,2,1,4};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println("========");
        int[] arr1 = {9,1,2,5,7,4,8,6,3,5};
        /*shellSort(arr1);
        System.out.println(Arrays.toString(arr1));
        System.out.println("========");*/
        /*selectSort(arr1);
        System.out.println(Arrays.toString(arr1));
        System.out.println("========");*/
        /*heapSort(arr1);
        System.out.println(Arrays.toString(arr1));
        System.out.println("========");*/
        /*quickSort(arr1);
        System.out.println(Arrays.toString(arr1));
        System.out.println("========");*/
        mergeSort(arr1);
        System.out.println(Arrays.toString(arr1));
        System.out.println("========");

    }
}
